/**
 * This file is part of gapro library.
 * 
 * gapro library is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General
 * Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any
 * later version.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
 * details.
 * 
 * You should have received a copy of the GNU Lesser General Public License along with this program. If not, see
 * <http://www.gnu.org/licenses/>
 * 
 * Copyright 2012 Vinay Penmatsa. All rights reserved.
 * 
 */
package org.stupidwhiz.gapro.core;

/**
 * Represents a set of linear system of equations Provides operations to solve the equations
 * 
 * @author Vinay Penmatsa
 * @since 1.0
 * 
 */
public class LinearSystem {

    public static final int SOLUTIONS_ONE = 1;
    public static final int SOLUTIONS_NONE = 0;
    public static final int SOLUTIONS_INFINITE = -1;

    private Fraction[][] matrix;

    /**
     * Constructs a LinearEquation with augmented matrix
     * 
     * @param matrix
     */
    public LinearSystem(Fraction[][] matrix) {
        if(matrix.length == 0)
            throw new IllegalArgumentException("Empty matrix");
        if(matrix[0].length == 0)
            throw new IllegalArgumentException("Empty matrix");
        if(matrix.length != matrix[0].length + 1)
            throw new IllegalArgumentException("Augmented matrix expected");

        this.matrix = matrix;
    }

    /**
     * Constructs a LinearEquation with augmented matrix Each element in the array is comma(,) separated string of a
     * column vector
     * 
     * So, if the set of equations is 3x + 2y - 3z = -13; 4x - 3y + 6z = 7; x - z = -5;
     * 
     * the column vectors are 3,4,1 2,-3,0 -3,6,-1 -13,7,-5
     * 
     * @param matrix
     */
    public LinearSystem(String[] matrix) {
        if(matrix.length == 0)
            throw new IllegalArgumentException("Empty matrix");
        String[] splits = matrix[0].split(",");

        Fraction[][] m = new Fraction[matrix.length][matrix.length - 1];

        for(int i = 0; i < matrix.length; i++) {
            splits = matrix[i].split(",");
            if(matrix.length != splits.length + 1)
                throw new IllegalArgumentException("Augmented matrix expected");
            for(int j = 0; j < splits.length; j++) {
                m[i][j] = Fraction.createFraction(splits[j]);
            }
        }
        this.matrix = m;
    }

    /**
     * Solves the linear equation set.
     * 
     * Returns SOLUTIONS_ONE(1) if there is only one solution SOLUTIONS_NONE(0) if there is NO solution
     * SOLUTIONS_INFINITE(-1) if there are infinite solutions
     * 
     * @return the solution indicator
     */
    public int solve() {
        int row = 0; // row index

        int rowLength = matrix[0].length;
        int colLength = matrix.length;

        // loop columns 0 to colLength-1

        for(int col = 0; col < colLength; col++) {
            int k = findMaxInRowFromIndex(matrix[row], row);
            if(k == -1)
                continue;
            if(k != row) {
                exchangeRows(k, row);
            }
            Fraction m = matrix[col][row];
            multiplyRow(row, m);
            reduceRow(row, col);
            row++;
            if(row == rowLength)
                break;
        }

        return examineSolution();
    }

    private int examineSolution() {
        int rowLength = matrix[0].length;
        Fraction oneF = new Fraction(1);
        Fraction zeroF = new Fraction(0);

        // Test for one solution
        boolean foundOne = true;
        for(int j = 0; j < rowLength; j++) {
            for(int i = 0; i < rowLength; i++) {
                if(i == j && !oneF.equals(matrix[i][j])) {
                    foundOne = false;
                }
                if(i != j && !zeroF.equals(matrix[i][j])) {
                    foundOne = false;
                }
                if(!foundOne)
                    break;
            }
            if(!foundOne)
                break;
        }

        if(foundOne)
            return SOLUTIONS_ONE;

        // Test all zeros
        boolean infiniteFound = false;
        boolean noneFound = false;
        for(int j = 0; j < rowLength; j++) {
            boolean allZeros = true;
            for(int i = 0; i < rowLength; i++) {
                if(!zeroF.equals(matrix[i][j])) {
                    allZeros = false;
                    break;
                }
            }
            if(allZeros) {
                // Check the constant vector
                if(zeroF.equals(matrix[rowLength][j]))
                    infiniteFound = true; // infinite
                else
                    noneFound = true; // infinite
                break;
            }
        }

        if(noneFound)
            return SOLUTIONS_NONE;

        if(infiniteFound)
            return SOLUTIONS_INFINITE;

        return SOLUTIONS_NONE;
    }

    private int findMaxInRowFromIndex(Fraction[] row, int index) {
        Fraction max = row[index];
        int k = index;
        for(int i = index; i < row.length; i++) {
            if(row[i].compareToAbs(max) > 0) {
                max = row[i];
                k = i;
            }
        }
        if(max.getNumerator() == 0)
            k = -1;
        return k;
    }

    private void exchangeRows(int k, int row) {
        for(int j = 0; j < matrix.length; j++) { // col
            Fraction temp = matrix[j][k];
            matrix[j][k] = matrix[j][row];
            matrix[j][row] = temp;
        }
    }

    private void multiplyRow(int row, Fraction m) {
        Fraction invM = new Fraction(m.getDenominator(), m.getNumerator());
        for(int i = 0; i < matrix.length; i++) {
            matrix[i][row].multiply(invM);
        }
    }

    private void reduceRow(int row, int col) {
        for(int r = 0; r < matrix[0].length; r++) {
            if(r == row)
                continue;
            Fraction f1 = new Fraction(matrix[col][r].getNumerator(), matrix[col][r].getDenominator());
            for(int c = 0; c < matrix.length; c++) {

                Fraction f = new Fraction(f1.getNumerator(), f1.getDenominator());
                f.multiply(new Fraction(-1));
                f.multiply(matrix[c][row]);
                matrix[c][r].add(f);
            }
        }
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int j = 0, m = matrix.length; j < m; j++) {
            sb.append("<");
            for(int i = 0, n = matrix[0].length; i < n; i++) {
                sb.append(matrix[j][i] + (i == n - 1 ? "" : ","));
            }
            sb.append(">");
            if(j != m - 1)
                sb.append(" ");
        }
        return sb.toString();
    }
}
